Dijkstra's algorithm is a well-known greedy algorithm that solves the single-source shortest path problem for a directed graph with non-negative edge weights. For example, if the vertices (nodes) of the graph represent routers and networks, and edge weights represent links between pairs of routers or between routers and networks in a network, Dijkstra's algorithm can be used to find the shortest route between two points in the network. The well-known Open Shortest Path First (OSPF) routing protocol and Intermediate System to Intermediate System (ISIS) routing protocol, for example, use Dijkstra's algorithm in computing packet routes through Internet Protocol (IP) networks.
When a network link fails, the routers must typically compute new paths to replace those broken by the failed link. The IP Fast-Reroute (IPFRR) protocol has been proposed to reduce failure reaction time when this sort of local link failure occurs in an IP network. Atlas et al. provide a “Basic Specification for IP Fast-Reroute: Loop-free Alternates” in the document draft-ietf-rtgwg-ipfrr-spec-base-07 (Jul. 6, 2007), which is incorporated herein by reference. According to this document, IPFRR uses a pre-computed alternate next-hop in the event that the currently-selected primary next-hop fails, so that the alternate can be rapidly used to transmit packets when the failure is detected. A network with this feature is supposed to experience less traffic loss than a network without IPFRR. Atlas et al. describe an algorithm that may be used to perform the alternate next-hop computation.